package SearchAlgorithms;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

import Main.DrawNewMaze;
import Main.Operators;
import Maze.HorizontalTile;
import Maze.Maze;
import Maze.Mouse;
import Maze.VerticalTile;
import Tree.Node;
import Tree.OperatorsNode;
import Tree.Tree;

/**
 * 
 * This class is used to expand the node and return its children
 * 
 */
public class Expand {

	Node node;
	Operators operation;
	Tree tree;
	Maze maze;
	LinkedList<Node> children = new LinkedList<Node>();
	int heuristic = 0;
	boolean visualize;
	int depth;

	/**
	 * The constructor takes the node to be expanded and the tree and the
	 * operators that could be done and whether or not to visualize
	 * 
	 * @param n
	 * @param operators
	 * @param t
	 * @param visualize
	 * 
	 */
	public Expand(Node n, Operators operators, Tree t, boolean visualize) {
		node = n;
		operation = operators;
		tree = t;
		this.visualize = visualize;
	}

	/**
	 * The constructor takes the node to be expanded,the tree, the operators
	 * that could be done, which heuristic to do and whether or not to visualize
	 * 
	 * @param n
	 * @param operators
	 * @param t
	 * @param h
	 * @param visualize
	 */
	public Expand(Node n, Operators operators, Tree t, int h, boolean visualize) {
		node = n;
		operation = operators;
		tree = t;
		heuristic = h;
		this.visualize = visualize;
	}

	/**
	 * This method checks for all possible moves of the tiles and the mouse
	 * 
	 * @return the list of children
	 */
	public LinkedList<Node> expandNode() {

		this.maze = (Maze) node.getState();
		depth = node.getDepth();
		moveMouseRight();
		moveMouseLeft();
		moveVerticalUp();
		moveVerticalDown();
		moveHorizontalRight();
		moveHorizontalLeft();
		return children;
	}

	/**
	 * This method checks if the mouse is able to move 1 step to the right, if
	 * so a new node is created with the new maze which contains the updated
	 * position of the mouse
	 */
	public void moveMouseRight() {

		Mouse newMouse = copyMouse(maze.getMouse());

		int startX = maze.getMouse().getStartX();
		int endX = maze.getMouse().getEndX();
		int positionY = maze.getMouse().getEndY();

		if (endX != 5) {
			if (maze.getGrid()[(endX + 1)][positionY].equals(". ")) {
				ArrayList<VerticalTile> verticalTiles = copyVerticalTiles(maze
						.getVerticalTiles());
				ArrayList<HorizontalTile> horizontalTiles = copyHorizontalTile(maze
						.getHorizontalTiles());

				newMouse.setStartX(startX + 1);
				newMouse.setEndX(endX + 1);
				String[][] newGrid = DrawNewMaze.drawMaze(newMouse,
						verticalTiles, horizontalTiles);
				Maze newMaze = createMaze(newGrid, newMouse, verticalTiles,
						horizontalTiles);
				Operators operation = new OperatorsNode(newMouse, "Right");

				Node newNode = new Node(false, node, depth + 1, operation,
						newMaze);

				if (addNode(newNode)) {
					if (visualize) {
						System.out.println("Old position of mouse  start x  "
								+ maze.getMouse().getStartX() + "  end x  "
								+ maze.getMouse().getEndX());
						System.out.println("New postion of mouse start x  "
								+ newMaze.getMouse().getStartX() + "  end  "
								+ newMaze.getMouse().getEndX());
						System.out.println();
						System.out.println();
					}
				}
			}
		}
	}

	/**
	 * This method checks if the mouse is able to move 1 step to the left, if so
	 * a new node is created with the new maze which contains the updated
	 * position of the mouse
	 */
	public void moveMouseLeft() {

		Mouse newMouse = copyMouse(maze.getMouse());

		int startX = maze.getMouse().getStartX();
		int endX = maze.getMouse().getEndX();
		int positionY = maze.getMouse().getEndY();

		if (startX != 0) {
			if (maze.getGrid()[(startX - 1)][positionY].equals(". ")) {

				ArrayList<VerticalTile> verticalTiles = copyVerticalTiles(maze
						.getVerticalTiles());
				ArrayList<HorizontalTile> horizontalTiles = copyHorizontalTile(maze
						.getHorizontalTiles());

				newMouse.setStartX(startX - 1);
				newMouse.setEndX(endX - 1);
				String[][] newGrid = DrawNewMaze.drawMaze(newMouse,
						verticalTiles, horizontalTiles);
				Maze newMaze = createMaze(newGrid, newMouse, verticalTiles,
						horizontalTiles);

				Operators operation = new OperatorsNode(newMouse, "Left");
				Node newNode = new Node(false, node, depth + 1, operation,
						newMaze);

				if (addNode(newNode)) {
					if (visualize) {
						System.out.println("Old position of mouse  start x  "
								+ maze.getMouse().getStartX() + "  end x  "
								+ maze.getMouse().getEndX());
						System.out.println("New postion of mouse start x  "
								+ newMaze.getMouse().getStartX() + "  end  "
								+ newMaze.getMouse().getEndX());
						System.out.println();
						System.out.println();
					}
				}
			}
		}
	}

	/**
	 * This method checks if the any of the vertical tiles are able to move up,
	 * if any of the tiles moves up a node is created with the new position of
	 * the moved tile
	 */
	public void moveVerticalUp() {

		ArrayList<VerticalTile> newVerticalTiles = copyVerticalTiles(maze
				.getVerticalTiles());
		int i = 0;

		for (VerticalTile verticalTile : newVerticalTiles) {

			int positionX = verticalTile.getEndX();
			int startY = verticalTile.getStartY();
			int endY = verticalTile.getEndY();

			if (startY != 0) {
				if (maze.getGrid()[positionX][startY - 1].equals(". ")) {

					ArrayList<VerticalTile> newVerticalTiles2 = copyVerticalTiles(maze
							.getVerticalTiles());

					newVerticalTiles2.get(i).setStartY(startY - 1);
					newVerticalTiles2.get(i).setEndY(endY - 1);

					ArrayList<HorizontalTile> newHorizontalTiles = copyHorizontalTile(maze
							.getHorizontalTiles());
					Mouse newMouse = copyMouse(maze.getMouse());

					String[][] newGrid = DrawNewMaze.drawMaze(newMouse,
							newVerticalTiles2, newHorizontalTiles);
					Maze newMaze = createMaze(newGrid, newMouse,
							newVerticalTiles2, newHorizontalTiles);

					Operators operation = new OperatorsNode(verticalTile, "UP");
					Node newNode = new Node(false, node, depth + 1, operation,
							newMaze);
					if (addNode(newNode)) {
						if (visualize) {
							System.out.println("Old starty v "
									+ maze.getVerticalTiles().get(i).getName()
									+ " "
									+ maze.getVerticalTiles().get(i)
											.getStartY() + "  new  v  "
									+ newVerticalTiles2.get(i).getName()
									+ " start y "
									+ newVerticalTiles2.get(i).getStartY());
							System.out.println("Old endy v "
									+ maze.getVerticalTiles().get(i).getName()
									+ " "
									+ maze.getVerticalTiles().get(i).getEndY()
									+ "  new  v  "
									+ newVerticalTiles2.get(i).getName()
									+ " end y "
									+ newVerticalTiles2.get(i).getEndY());
							System.out.println();
							System.out.println();
						}
					}
				}
			}
			i++;
		}
	}

	/**
	 * This method checks if the any of the vertical tiles are able to move
	 * down, if any of the tiles moves down a node is created with the new
	 * position of the moved tile
	 */
	public void moveVerticalDown() {

		ArrayList<VerticalTile> newVerticalTiles = copyVerticalTiles(maze
				.getVerticalTiles());
		int i = 0;

		for (VerticalTile verticalTile : newVerticalTiles) {

			int positionX = verticalTile.getEndX();
			int startY = verticalTile.getStartY();
			int endY = verticalTile.getEndY();

			if (endY != 5) {
				if (maze.getGrid()[positionX][endY + 1].equals(". ")) {

					ArrayList<VerticalTile> newVerticalTiles2 = copyVerticalTiles(maze
							.getVerticalTiles());

					newVerticalTiles2.get(i).setStartY(startY + 1);
					newVerticalTiles2.get(i).setEndY(endY + 1);

					ArrayList<HorizontalTile> newHorizontalTiles = copyHorizontalTile(maze
							.getHorizontalTiles());
					Mouse newMouse = copyMouse(maze.getMouse());

					String[][] newGrid = DrawNewMaze.drawMaze(newMouse,
							newVerticalTiles2, newHorizontalTiles);
					Maze newMaze = createMaze(newGrid, newMouse,
							newVerticalTiles2, newHorizontalTiles);

					Operators operation = new OperatorsNode(verticalTile,
							"Down");
					Node newNode = new Node(false, node, depth + 1, operation,
							newMaze);
					if (addNode(newNode)) {
						if (visualize) {
							System.out.println("Old starty v "
									+ maze.getVerticalTiles().get(i).getName()
									+ " "
									+ maze.getVerticalTiles().get(i)
											.getStartY() + "  new  v  "
									+ newVerticalTiles2.get(i).getName()
									+ " start y "
									+ newVerticalTiles2.get(i).getStartY());
							System.out.println("Old endy v "
									+ maze.getVerticalTiles().get(i).getName()
									+ " "
									+ maze.getVerticalTiles().get(i).getEndY()
									+ "  new  v  "
									+ newVerticalTiles2.get(i).getName()
									+ " end y "
									+ newVerticalTiles2.get(i).getEndY());
							System.out.println();
							System.out.println();
						}
					}
				}
			}
			i++;
		}
	}

	/**
	 * This method checks if the any of the horizontal tiles are able to move
	 * right, if any of the tiles moves right a node is created with the new
	 * position of the moved tile
	 */
	public void moveHorizontalRight() {

		ArrayList<HorizontalTile> newHorizontalTiles = copyHorizontalTile(maze
				.getHorizontalTiles());
		int i = 0;

		for (HorizontalTile horizontalTile : newHorizontalTiles) {

			int startX = horizontalTile.getStartX();
			int endX = horizontalTile.getEndX();
			int positionY = horizontalTile.getEndY();

			if (endX != 5) {
				if (maze.getGrid()[(endX + 1)][positionY].equals(". ")) {

					ArrayList<HorizontalTile> newHorizontalTiles2 = copyHorizontalTile(maze
							.getHorizontalTiles());

					newHorizontalTiles2.get(i).setStartX(startX + 1);
					newHorizontalTiles2.get(i).setEndX(endX + 1);

					ArrayList<VerticalTile> newVerticalTiles = copyVerticalTiles(maze
							.getVerticalTiles());

					Mouse newMouse = copyMouse(maze.getMouse());
					String[][] newGrid = DrawNewMaze.drawMaze(newMouse,
							newVerticalTiles, newHorizontalTiles2);
					Maze newMaze = createMaze(newGrid, newMouse,
							newVerticalTiles, newHorizontalTiles2);

					Operators operation = new OperatorsNode(horizontalTile,
							"RIGHT");
					Node newNode = new Node(false, node, depth + 1, operation,
							newMaze);
					if (addNode(newNode)) {
						if (visualize) {
							System.out.println("Old startx h "
									+ maze.getHorizontalTiles().get(i)
											.getName()
									+ " "
									+ maze.getHorizontalTiles().get(i)
											.getStartX() + "  new  h  "
									+ newHorizontalTiles2.get(i).getName()
									+ " start x "
									+ newHorizontalTiles2.get(i).getStartX());
							System.out.println("Old endx h "
									+ maze.getHorizontalTiles().get(i)
											.getName()
									+ " "
									+ maze.getHorizontalTiles().get(i)
											.getEndX() + "  new  h  "
									+ newHorizontalTiles2.get(i).getName()
									+ " end h "
									+ newHorizontalTiles2.get(i).getEndX());
							System.out.println();
							System.out.println();
						}
					}
				}
			}
			i++;
		}
	}

	/**
	 * This method checks if the any of the horizontal tiles are able to move
	 * left, if any of the tiles moves left a node is created with the new
	 * position of the moved tile
	 */
	private void moveHorizontalLeft() {

		ArrayList<HorizontalTile> newHorizontalTiles = copyHorizontalTile(maze
				.getHorizontalTiles());

		int i = 0;

		for (HorizontalTile horizontalTile : newHorizontalTiles) {

			int startX = horizontalTile.getStartX();
			int endX = horizontalTile.getEndX();
			int positionY = horizontalTile.getEndY();

			if (startX != 0) {
				if (maze.getGrid()[(startX - 1)][positionY].equals(". ")) {

					ArrayList<HorizontalTile> newHorizontalTiles2 = copyHorizontalTile(maze
							.getHorizontalTiles());

					newHorizontalTiles2.get(i).setStartX(startX - 1);
					newHorizontalTiles2.get(i).setEndX(endX - 1);

					ArrayList<VerticalTile> newVerticalTiles = copyVerticalTiles(maze
							.getVerticalTiles());
					Mouse newMouse = copyMouse(maze.getMouse());
					String[][] newGrid = DrawNewMaze.drawMaze(newMouse,
							newVerticalTiles, newHorizontalTiles2);
					Maze newMaze = createMaze(newGrid, newMouse,
							newVerticalTiles, newHorizontalTiles2);

					Operators operation = new OperatorsNode(horizontalTile,
							"LEFT");
					Node newNode = new Node(false, node, depth + 1, operation,
							newMaze);

					if (addNode(newNode)) {
						if (visualize) {
							System.out.println("Old startx h "
									+ maze.getHorizontalTiles().get(i)
											.getName()
									+ " "
									+ maze.getHorizontalTiles().get(i)
											.getStartX() + "  new  h  "
									+ newHorizontalTiles2.get(i).getName()
									+ " start x "
									+ newHorizontalTiles2.get(i).getStartX());
							System.out.println("Old endx h "
									+ maze.getHorizontalTiles().get(i)
											.getName()
									+ " "
									+ maze.getHorizontalTiles().get(i)
											.getEndX() + "  new  h  "
									+ newHorizontalTiles2.get(i).getName()
									+ " end h "
									+ newHorizontalTiles2.get(i).getEndX());
							System.out.println();
							System.out.println();
						}
					}
				}
			}
			i++;
		}
	}

	/**
	 * This methods takes the parameters in order to create the new maze
	 * 
	 * @param grid
	 * @param mouse
	 * @param vTiles
	 * @param hTiles
	 * @return the created maze
	 */
	private Maze createMaze(String[][] grid, Mouse mouse,
			ArrayList<VerticalTile> vTiles, ArrayList<HorizontalTile> hTiles) {
		Maze newMaze = new Maze();
		newMaze.setGrid(grid);
		newMaze.setHorizontalTiles(hTiles);
		newMaze.setMouse(mouse);
		newMaze.setVerticalTiles(vTiles);
		return newMaze;

	}

	/**
	 * 
	 * @param mouse
	 * @return a new mouse which is identical to the mouse from the parameter
	 */
	private Mouse copyMouse(Mouse mouse) {
		Mouse newMouse = new Mouse();

		newMouse.setEndX(mouse.getEndX());
		newMouse.setStartX(mouse.getStartX());
		newMouse.setEndY(mouse.getEndY());
		newMouse.setStartY(mouse.getStartY());
		newMouse.setName("M ");
		return newMouse;
	}

	/**
	 * 
	 * @param verticalTiles
	 * @return a list of vertical tiles identical to the list in the parameter
	 */
	private ArrayList<VerticalTile> copyVerticalTiles(
			ArrayList<VerticalTile> verticalTiles) {

		ArrayList<VerticalTile> newVerticalTiles = new ArrayList<VerticalTile>();

		for (VerticalTile verticalTile : verticalTiles) {
			VerticalTile newVertical = new VerticalTile();
			newVertical.setEndX(verticalTile.getEndX());
			newVertical.setEndY(verticalTile.getEndY());
			newVertical.setLength(verticalTile.getLength());
			newVertical.setName(verticalTile.getName());
			newVertical.setStartX(verticalTile.getStartX());
			newVertical.setStartY(verticalTile.getStartY());
			newVerticalTiles.add(newVertical);
		}
		return newVerticalTiles;

	}

	/**
	 * 
	 * @param horizontalTiles
	 * @return a list of horizontal tiles which is identical to the one in the
	 *         parameter
	 */
	private ArrayList<HorizontalTile> copyHorizontalTile(
			ArrayList<HorizontalTile> horizontalTiles) {

		ArrayList<HorizontalTile> newHorizontalTiles = new ArrayList<HorizontalTile>();

		for (HorizontalTile horizontalTile : horizontalTiles) {
			HorizontalTile newHorizontal = new HorizontalTile();
			newHorizontal.setEndX(horizontalTile.getEndX());
			newHorizontal.setEndY(horizontalTile.getEndY());
			newHorizontal.setName(horizontalTile.getName());
			newHorizontal.setStartX(horizontalTile.getStartX());
			newHorizontal.setStartY(horizontalTile.getStartY());
			newHorizontalTiles.add(newHorizontal);
		}

		return newHorizontalTiles;
	}

	/**
	 * Adds the new node to the list of children if and only if it is unique
	 * 
	 * @param newNode
	 * @return whether or not it is added
	 */
	private boolean addNode(Node newNode) {

		for (Node checkNode : tree.getNodes()) {
			Maze maze1 = (Maze) newNode.getState();
			Maze maze2 = (Maze) checkNode.getState();
			if (Arrays.deepEquals(maze1.getGrid(), maze2.getGrid())) {

				return false;
			}
		}
		Maze maze = (Maze) newNode.getState();
		if (visualize) {
			for (int i = 0; i < 6; i++) {
				for (int j = 0; j < 6; j++) {

					System.out.print(maze.getGrid()[j][i]);
				}
				System.out.println();
			}
			System.out.println();
			System.out.println();
		}
		if (heuristic == 1)
			newNode = setHeuristic1(newNode);
		if (heuristic == 2)
			newNode = setHeuristic2(newNode);
		if (heuristic == 3)
			newNode = setHeuristic3(newNode);
		if (heuristic == 4)
			newNode = setHeuristic4(newNode);

		children.add(newNode);
		tree.getNodes().add(newNode);
		return true;
	}

	/**
	 * Sets the heuristic for the node
	 * 
	 * @param newNode
	 * @return the newNode after setting its heuristic
	 */
	private Node setHeuristic1(Node newNode) {
		Maze maze = (Maze) newNode.getState();
		// heuristic1
		boolean set = false;
		for (HorizontalTile hTile : maze.getHorizontalTiles()) {
			if (hTile.getStartY() == 2) {
				newNode.setHeuristic(10000000);
				set = true;
				break;
			}
		}
		int h = 0;
		if (!set) {

			for (VerticalTile vTile : maze.getVerticalTiles()) {
				if (vTile.getStartX() > maze.getMouse().getEndX()) {
					if (vTile.getLength() == 2) {
						if (vTile.getEndY() == 2 || vTile.getStartY() == 2)
							h += 2;
					} else {
						if (vTile.getStartY() == 2) {
							h++;
						} else {
							if (vTile.getEndY() == 2) {
								h += 3;
							} else {
								if (vTile.getEndY() == 3) {
									h += 2;
								}

							}
						}
					}
				}
			}

			newNode.setHeuristic(h);
		}

		System.out.println("heuristic " + newNode.getHeuristic());

		return newNode;
	}

	/**
	 * Sets the heuristic for the node
	 * 
	 * @param newNode
	 * @return the newNode after setting its heuristic
	 */
	private Node setHeuristic2(Node newNode) {
		Maze maze = (Maze) newNode.getState();
		boolean set = false;
		for (HorizontalTile hTile : maze.getHorizontalTiles()) {
			if (hTile.getStartY() == 2) {
				newNode.setHeuristic(10000000);
				set = true;
				break;
			}
		}
		if (!set) {
			int h = 0;
			for (VerticalTile vTile : maze.getVerticalTiles()) {
				if (vTile.getStartX() > maze.getMouse().getEndX()) {
					h = checkVAtRow2(newNode, vTile, h);
				}
			}
			newNode.setHeuristic(h);
		}
		System.out.println("heuristic " + newNode.getHeuristic());
		return newNode;
	}

	/**
	 * Sets the heuristic for the node
	 * 
	 * @param newNode
	 * @return the newNode after setting its heuristic
	 */
	private Node setHeuristic3(Node newNode) {
		Maze maze = (Maze) newNode.getState();
		// heuristic1
		boolean set = false;
		for (HorizontalTile hTile : maze.getHorizontalTiles()) {
			if (hTile.getStartY() == 2) {
				newNode.setHeuristic(10000000);
				set = true;
				break;
			}
		}
		int f = 0;
		if (!set) {

			for (VerticalTile vTile : maze.getVerticalTiles()) {
				if (vTile.getStartX() > maze.getMouse().getEndX()) {
					if (vTile.getLength() == 2) {
						if (vTile.getEndY() == 2 || vTile.getStartY() == 2)
							f += 2;
					} else {
						if (vTile.getStartY() == 2) {
							f++;
						} else {
							if (vTile.getEndY() == 2) {
								f += 3;
							} else {
								if (vTile.getEndY() == 3) {
									f += 2;
								}

							}
						}
					}
				}
			}

			f += newNode.getDepth();
			newNode.setHeuristic(f);
		}

		System.out.println("heuristic " + newNode.getHeuristic());

		return newNode;
	}

	/**
	 * Sets the heuristic for the node
	 * 
	 * @param newNode
	 * @return the newNode after setting its heuristic
	 */
	private Node setHeuristic4(Node newNode) {
		Maze maze = (Maze) newNode.getState();
		boolean set = false;
		for (HorizontalTile hTile : maze.getHorizontalTiles()) {
			if (hTile.getStartY() == 2) {
				newNode.setHeuristic(10000000);
				set = true;
				break;
			}
		}
		if (!set) {
			int h = 0;
			for (VerticalTile vTile : maze.getVerticalTiles()) {
				if (vTile.getStartX() > maze.getMouse().getEndX()) {
					h = checkVAtRow2(newNode, vTile, h);
				}
			}
			int f = h + newNode.getDepth();
			newNode.setHeuristic(f);
		}
		System.out.println("heuristic " + newNode.getHeuristic());
		return newNode;
	}

	/**
	 * Checks whether there was a vertical Tile at row 2 and if it was free to
	 * move up and down
	 * 
	 * @param newNode
	 * @param vTile
	 * @param h
	 * @return the new heuristic computed
	 */
	private int checkVAtRow2(Node newNode, VerticalTile vTile, int h) {
		Maze newMaze = (Maze) newNode.getState();
		if (vTile.getLength() == 2) {
			if (vTile.getStartY() == 2) {
				String up1 = newMaze.getGrid()[vTile.getStartX()][1];
				String up2 = newMaze.getGrid()[vTile.getStartX()][0];
				String down1 = newMaze.getGrid()[vTile.getStartX()][4];
				if (down1.charAt(0) == '.') {
					h++;
					return h;
				}
				if ((up1.charAt(0) == '.') && up2.charAt(0) == '.') {
					h += 2;
					return h;
				}
				if (down1.charAt(0) == 'V') {
					return 1000000;
				}
				if (down1.charAt(0) == 'H') {
					HorizontalTile hTile = getHorizontalTile(newMaze,
							vTile.getStartX(), 4);
					return 1 + h
							+ checkNearH(newNode, hTile, vTile.getEndX(), h);
				}
				if (up1.charAt(0) == 'V') {
					return 1000000;
				}
				if (up1.charAt(0) == 'H') {
					HorizontalTile hTile = getHorizontalTile(newMaze,
							vTile.getStartX(), 1);
					return h + 1
							+ checkNearH(newNode, hTile, vTile.getEndX(), h);
				}
				if (up2.charAt(0) == 'H') {
					HorizontalTile hTile = getHorizontalTile(newMaze,
							vTile.getStartX(), 0);
					return h + 2
							+ checkNearH(newNode, hTile, vTile.getEndX(), h);
				}

			} else {
				if (vTile.getEndY() == 2) {
					String up1 = newMaze.getGrid()[vTile.getStartX()][0];
					String down1 = newMaze.getGrid()[vTile.getStartX()][3];
					String down2 = newMaze.getGrid()[vTile.getStartX()][4];

					if (up1.charAt(0) == '.') {
						h++;
						return h;
					}
					if ((down1.charAt(0) == '.') && (down2.charAt(0) == '.')) {
						h += 2;
						return h;
					}
					if (up1.charAt(0) == 'H') {
						HorizontalTile hTile = getHorizontalTile(newMaze,
								vTile.getStartX(), 0);
						return h
								+ 1
								+ checkNearH(newNode, hTile, vTile.getEndX(), h);
					}
					if (down1.charAt(0) == 'V') {
						return 1000000;
					}
					if (down1.charAt(0) == 'H') {
						HorizontalTile hTile = getHorizontalTile(newMaze,
								vTile.getStartX(), 3);
						return h
								+ 1
								+ checkNearH(newNode, hTile, vTile.getEndX(), h);
					}
					if (down2.charAt(0) == 'V') {
						return 1000000;
					}
					if (down2.charAt(0) == 'H') {
						HorizontalTile hTile = getHorizontalTile(newMaze,
								vTile.getStartX(), 4);
						return h
								+ 2
								+ checkNearH(newNode, hTile, vTile.getEndX(), h);
					}
				}
			}
		} else { // vtile.getlenght()==3
			if (vTile.getEndY() == 2 || vTile.getStartY() == 2
					|| vTile.getStartY() == 1) {
				String Y5 = newMaze.getGrid()[vTile.getEndX()][5];
				String Y4 = newMaze.getGrid()[vTile.getEndX()][4];
				String Y3 = newMaze.getGrid()[vTile.getEndX()][3];
				if ((vTile.getStartY() == 2)) {
					if (Y5.charAt(0) == '.') {
						h++;
						return h;
					}
					if (Y5.charAt(0) == 'H') {
						HorizontalTile hTile = getHorizontalTile(newMaze,
								vTile.getStartX(), 5);
						return h
								+ 1
								+ checkNearH(newNode, hTile, vTile.getEndX(), h);
					}
				}
				if (vTile.getEndY() == 3) {
					if ((Y4.charAt(0) == '.') && (Y5.charAt(0) == '.')) {
						h += 2;
						return h;
					}
					if (Y4.charAt(0) == 'V') {
						return 1000000;

					}
					if (Y4.charAt(0) == 'H') {
						HorizontalTile hTile = getHorizontalTile(newMaze,
								vTile.getStartX(), 4);
						return h
								+ 2
								+ checkNearH(newNode, hTile, vTile.getEndX(), h);
					}
					if (Y5.charAt(0) == 'H') {
						HorizontalTile hTile = getHorizontalTile(newMaze,
								vTile.getStartX(), 5);
						return h
								+ 2
								+ checkNearH(newNode, hTile, vTile.getEndX(), h);
					}
				}

				if ((vTile.getEndY() == 2)) {
					if ((Y3.charAt(0) == '.') && (Y4.charAt(0) == '.')
							&& (Y5.charAt(0) == '.')) {
						h += 3;
						return h;
					}
					if (Y3.charAt(0) == 'V') {
						return 1000000;
					}
					if (Y3.charAt(0) == 'H') {
						HorizontalTile hTile = getHorizontalTile(newMaze,
								vTile.getStartX(), 3);
						return h
								+ 3
								+ checkNearH(newNode, hTile, vTile.getEndX(), h);
					}
					if (Y4.charAt(0) == 'V') {
						return 1000000;
					}
					if (Y4.charAt(0) == 'H') {
						HorizontalTile hTile = getHorizontalTile(newMaze,
								vTile.getStartX(), 4);
						return h
								+ 3
								+ checkNearH(newNode, hTile, vTile.getEndX(), h);
					}
					if (Y5.charAt(0) == 'H') {
						HorizontalTile hTile = getHorizontalTile(newMaze,
								vTile.getStartX(), 5);
						return h
								+ 3
								+ checkNearH(newNode, hTile, vTile.getEndX(), h);
					}

				}
			}
		}
		return h;
	}

	/**
	 * Check if the horizontal is able to move
	 * 
	 * @param newNode
	 * @param hTile
	 * @param i
	 * @param h
	 * @return the new heuristic
	 */
	private int checkNearH(Node newNode, HorizontalTile hTile, int i, int h) {
		Maze newMaze = (Maze) newNode.getState();
		int startX;
		int endX;
		boolean endXOverV = false;
		if (hTile.getStartX() == i) {
			startX = i;
			endX = i + 1;
		} else {
			endX = i;
			startX = i - 1;
			endXOverV = true;
		}
		if (endXOverV) {
			if (endX != 5) {
				if (newMaze.getGrid()[endX + 1][hTile.getEndY()]
						.equalsIgnoreCase(". ")) {
					h += 2;
					return h;

				}
				if (startX != 0) {
					if (newMaze.getGrid()[startX - 1][hTile.getEndY()]
							.equalsIgnoreCase(". ")) {
						h++;
						return h;
					}
				}
			}
			return h + 10;
		}
		if (startX != 0) {
			if (newMaze.getGrid()[startX - 1][hTile.getEndY()]
					.equalsIgnoreCase(". ")) {
				h += 2;
				return h;
			}
			if (endX != 5) {
				if (newMaze.getGrid()[endX + 1][hTile.getEndY()]
						.equalsIgnoreCase(". ")) {
					h++;
					return h;
				}
			}
			return h + 10;
		}

		return h + 10;
	}

	/**
	 * 
	 * @param maze1
	 * @param i
	 * @param j
	 * @return the horizontal tile that has position i & j
	 */
	private HorizontalTile getHorizontalTile(Maze maze1, int i, int j) {
		for (HorizontalTile horizontalTile : maze1.getHorizontalTiles()) {
			if (horizontalTile.getEndY() == j) {
				if (horizontalTile.getStartX() == i
						|| horizontalTile.getEndX() == i) {
					return horizontalTile;
				}
			}
		}
		return null;
	}

}